As is well known, a solid state drive (SSD) is a data storage device that uses a NAND-based flash memory to store data. The NAND-based flash memory is a non-volatile memory. After data are written to the flash memory, if no power is supplied to the flash memory, the data are still retained in the flash memory.
Depending on the designed configurations, the NAND-based flash memories may be classified into three types, i.e. a single-level cell (SLC) flash memory, a multi-level cell (MLC) flash memory and a triple-level cell (TLC) flash memory.
The SLC flash memory has a faster accessing speed, higher cost, and a larger number of erase cycles (e.g. about several ten thousands of erase cycles). However, the SLC flash memory can store only one bit of data per cell. The TLC flash memory has a slower accessing speed, lower cost, and less number of erase cycles (e.g. lower than one thousand erase cycles). However, the TLC flash memory can store three bits of data per cell. The MLC flash memory has the intermediate properties between the SLC flash memory and the TLC flash memory. The accessing speed and the cost of the MLC flash memory are lower than the SLC flash memory but higher than the TLC flash memory. Generally, the MLC flash memory has one thousand to five thousand erase cycles, and stores two bits of data per cell. In other words, if the cell numbers are identical, the TLC flash memory has the largest capacity, and the SLC flash memory has the smallest capacity.
FIG. 1 is a schematic functional block diagram illustrating a conventional solid state drive. As shown in FIG. 1, the solid state drive 10 comprises a controlling unit 101 and a flash memory 105. The flash memory 105 is accessible by the controlling unit 101 through an internal bus 104. In addition, the controlling unit 101 is in communication with a host 12 through an external bus 20. Consequently, commands and data can be exchanged between the controlling unit 101 and the host 12. Generally, the external bus 20 is a USB bus, an IEEE 1394 bus, an SATA bus, or the like. The flash memory 105 is for example a SLC flash memory, a MLC flash memory or a TLC flash memory.
Moreover, the controlling unit 101 comprises a mapping unit 107 for managing the data within the flash memory 105. The mapping unit 107 is, for example, a static random access memory (SRAM) or a dynamic random access memory (DRAM). The mapping unit 107 at least comprises one logical-to-physical table (L2P table) and a bitmap table. In the L2P table, the relationships between the logical allocation addresses (LAA) from the host 12 and the physical allocation addresses (PAA) of the flash memory 105 are recorded. The bitmap table records whether the data in each page of the flash memory 105 is a valid data or an invalid data.
However, if the solid state drive 10 is powered off, the data in the L2P table and the bitmap table of the mapping unit 107 will be deleted. Once the solid state drive 10 is powered on again, the L2P table and the bitmap table should be reconstructed by the controlling unit 101, so that the solid state drive 10 can be normally operated.
Generally, the flash memory 105 comprises plural blocks. Each block comprises plural pages (or sectors), for example 64 pages. Each page is typically 4K bytes in size. Due to the inherent properties of the flash memory 105, at least one page is written at a time during the writing operation is performed, and the erasing operation is performed in a block-wise fashion.
Due to the inherent properties of the flash memory 105, if the data of a specified page of a block needs to be corrected, the controlling unit 101 cannot directly correct the data of the specified page. Whereas, the data to be corrected is written into another blank page by the controlling unit 101. Under this circumstance, the specified (old) page is considered as an invalid page, and the data contained therein is considered as an invalid data. Moreover, after many times of accessing actions by the host 12, the flash memory 105 may contain a great number of invalid pages and invalid data, which occupy a lot of space of the flash memory 105. For effectively managing the data of each block, a garbage collection process is provided. The garbage collection process is a process of collecting valid data of each block and rewriting the valid data into another block.
Hereinafter, a conventional data storing method for the flash memory will be illustrated with reference to FIGS. 2A˜2F.
As shown in FIG. 2A, it is assumed that the flash memory 105 has four blocks (BLOCK_0˜BLOCK_3). Each block has eight pages. Each page corresponds to a physical allocation address (PAA). The four blocks as shown in FIG. 2A are all blank blocks. The physical allocation addresses of the zero-th block BLOCK_0 are PAA(00)˜PAA(07). The physical allocation addresses of the first block BLOCK_1 are PAA(08)˜PAA(0F). The physical allocation addresses of the second block BLOCK_2 are PAA(10)˜PAA(17). The physical allocation addresses of the third block BLOCK_3 are PAA(18)˜PAA(1F). Moreover, one of the blocks (e.g. the first block BLOCK_1) may be set as an open block by the controlling unit 101, and the data can be written into the open block.
As shown in FIG. 2B, if the host 12 issues seven logical allocation addresses (LAA) and corresponding write data (D0˜D6) to the flash memory 105, these data are sequentially written into the first block BLOCK_1 by the controlling unit 101. In addition, the last page of the first block BLOCK_1 is retained by the controlling unit 101, and all physical-to-logical data of the first block BLOCK_1 (i.e. the P2L-data1 of the first block BLOCK_1) are filled into the last page. Then, the first block BLOCK_1 is set as a close block. Then, another block (e.g. the second block BLOCK_2) is set as an open clock. In other words, the close block is the block where the writing operation has been completed.
As shown in FIG. 2C, the host 12 issues seven logical allocation addresses and corresponding write data (D1′, D6′, D7, D8, D5′, D9, D2′) to the flash memory 105. The data D1, D6, D5 and D2 in the first block BLOCK_1 are replaced by the data D1′, D6′, D5′ and D2′, respectively. These data are sequentially written into the second block BLOCK_2 by the controlling unit 101. Moreover, the data D1, D6, D5 and D2 in PAA(09), PAA(0A), PAA(0D) and PAA(0E) of the first block BLOCK_1 are set as invalid data, which are indicated as oblique lines. In addition, the last page of the second block BLOCK_2 is retained by the controlling unit 101, and all physical-to-logical data of the second block BLOCK_2 (i.e. the P2L-data2 of the second block BLOCK_2) are filled into the last page. Then, the second block BLOCK_2 is set as a close block. Then, another block (e.g. the zero-th block BLOCK_0) is set as an open clock.
As shown in FIG. 2D, the host 12 issues seven logical allocation addresses and corresponding write data (D0′, D9′, D10, D3′, D8′, D5″, D1″) to the flash memory 105. The data D0 and D3 in the first block BLOCK_1 are replaced by the data D0′ and D3′, respectively. The data D9, D8, D5′ and D1′ in the second block BLOCK_2 are replaced by the data D9′, D8′, D5″ and D1″, respectively. These data are sequentially written into the zero-th block BLOCK_0 by the controlling unit 101. Moreover, the data D0 and D3 in PAA(08) and PAA(0B) of the first block BLOCK_1 are set as invalid data, and the data D1′, D8, D5′ and D9 in PAA(10), PAA(13), PAA(14) and PAA(15) of the second block BLOCK_2 are set as invalid data. In addition, the last page of the zero-th block BLOCK_0 is retained by the controlling unit 101, and all physical-to-logical data of the zero-th block BLOCK_0 (i.e. the P2L-data0 of the zero-th block BLOCK_0) are filled into the last page. Then, the zero-th block BLOCK_0 is set as a close block. Then, another block (e.g. the third block BLOCK_3) is set as an open clock.
From the above discussions in FIGS. 2A˜2D, after many times of accessing actions by the host 12, the flash memory 105 may contain a great number of invalid data. Since the space of the flash memory is occupied by the invalid data, the writable space of the flash memory is gradually reduced. For solving the above drawbacks, the controlling unit 101 may perform a garbage collection process at a proper time. The garbage collection process is used for collecting valid data of each block and rewriting the valid data into another block. Generally, the garbage collection process is performed during the time that there is no accessing action between the host 12 and the solid state drive 10. If the garbage collection process is performed during the data accessing action, the performance of the solid state drive 10 will be deteriorated.
After the garbage collection process is performed, as shown in FIG. 2E, the valid data D4 in PAA(0C) of the first block BLOCK_1 is stored and forwarded to the open block (i.e. the third block BLOCK_3). In other words, after the garbage collection process is performed, the data D4 is moved to the PAA(18) of the third block BLOCK_3, and denoted as the data D4-G. Meanwhile, the data D4 in PAA(0C) of the first block BLOCK_1 is set as the invalid data.
Similarly, after the garbage collection process is performed, the valid data D6′, D7 and D2′ in PAA(11), PAA(12) and PAA(16) of the second block BLOCK_2 are stored and forwarded to the open block (i.e. the third block BLOCK_3). In other words, after the garbage collection process is performed, the data D6′, D7 and D2′ are respectively moved to PAA(19), PAA(1A) and PAA(1B) of the third block BLOCK_3, and denoted as the data D6′-G, D7-G and D2′-G. Meanwhile, the valid data D6′, D7 and D2′ in PAA(11), PAA(12) and PAA(16) of the second block BLOCK_2 are set as the invalid data.
Obviously, after the garbage collection process is performed, no valid data are included in PAA(08)˜PAA(0E) of the first block BLOCK_1 and PAA(10)˜PAA(16) of the second block BLOCK_2. In addition, the data P2L-data1 in PAA(0F) and the data P2L-data2 in PAA(17) are not available. Consequently, the first block BLOCK_1 and the second block BLOCK_2 may be erased as the blank blocks at any time by the controlling unit 101.
For example, as shown in FIG. 2F, the first block BLOCK_1 is erased as the blank block by the controlling unit 101 after the garbage collection process is performed. Then, the host 12 issues two logical allocation addresses and corresponding write data (D11, D12) to the flash memory 105. These data are sequentially written into the third block BLOCK_3 by the controlling unit 101.
Since the solid state drive 10 has the plug-and-play function, the solid state drive 10 is frequently suffered from an unexpected power failure. For example, if the solid state drive 10 is carelessly touched by the user, the external bus 20 is detached from the host 12 or the solid state drive 10, so that the solid state drive 10 is suffered from the unexpected power failure. Otherwise, if the user misunderstands that there is no accessing action between the host 12 and the solid state drive 10, the user may unplug the solid state drive 10 from the host 12. Under this circumstance, the solid state drive 10 is also suffered from the unexpected power failure.
Take the solid state drive 10 with the MLC flash memory or the TLC flash memory for example. When a data is being written into a specified page of a specified block, if the solid state drive 10 is suffered from an unexpected power failure, the data in the specified block is damaged and even the data in other pages are possibly damaged. Otherwise, after the solid state drive 10 is powered on again, all data in the specified block are gradually damaged or lost.
Therefore, there is a need of providing a method for preserving data integrity after the power failure.